package cn.orange.ch05_stack;

import java.util.LinkedList;

/**
 * LC84.柱状图中最大的矩形
 */
public class LC84 {
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 1];
        System.arraycopy(heights, 0, newHeights, 0, heights.length);
        int maxArea = 0;
        LinkedList<Integer> stk = new LinkedList<>();
        for (int i = 0; i < newHeights.length; i++) {
            int h = newHeights[i];
            while (!stk.isEmpty() && h < newHeights[stk.peek()]) {
                Integer pop = stk.pop();
                int hi = newHeights[pop];
                int leftIndex = -1;
                if (!stk.isEmpty()) {
                    leftIndex = stk.peek();
                }
                int wi = i - leftIndex - 1;
                maxArea = Math.max(maxArea, hi * wi);
            }
            stk.push(i);
        }
        return maxArea;
    }
    public static void main(String[] args) {
        LC84 alg = new LC84();
        System.out.println(alg.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
        System.out.println(alg.largestRectangleArea(new int[]{2, 1, 2}));
    }
}
